class Solution {
    private Integer[][] dp = new Integer[1001][1001];

    public int maximumScore(int[] nums, int[] multipliers) {
        return func(nums, multipliers, 0, 0);
    }

    private int func(int[] nums, int[] multipliers, int i, int j) {
        if (dp[i][j] != null) {
            return dp[i][j];
        }

        if (i == multipliers.length) {
            return 0;
        }

        int res = Math.max(nums[j] * multipliers[i] + func(nums, multipliers, i + 1, j + 1), nums[nums.length - i - 1 + j] * multipliers[i] + func(nums, multipliers, i + 1, j));

        dp[i][j] = res;
        return res;
    }
}
